class Solution {
    int[] row = new int[9];
    int[] col = new int[9];
    int[][] martrix = new int[3][3];
    public void solveSudoku(char[][] board) {
        //预处理
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    row[i] |= (1 << num);
                    col[j] |= (1 << num);
                    martrix[i/3][j/3] |= (1 << num);
                }
            }
        }
        dfs(board);
    }
    boolean dfs(char[][] board) {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') {
                    for(int k = 1; k <= 9; k++) {
                        if((row[i] & (1 << k)) == 0 && (col[j] & (1 << k)) == 0
                                && (martrix[i/3][j/3] & (1 << k)) == 0) {
                            row[i] |= (1 << k);
                            col[j] |= (1 << k);
                            martrix[i/3][j/3] |= (1 << k);
                            board[i][j] = (char)('0' + k);
                            if(!dfs(board)) {
                                //恢复现场
                                row[i] &= ~(1 << k);
                                col[j] &= ~(1 << k);
                                martrix[i/3][j/3] &= ~(1 << k);
                                board[i][j] = '.';
                            }
                        }
                    }
                    if(board[i][j] == '.') {
                        //说明没有合适的数字填入
                        return false;
                    }
                }
            }
        }
        return true;
    }
}